package LinkList;

public class item21 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode fakeHead = new ListNode(-1);
        ListNode p = list1;
        ListNode q = list2;
        ListNode tmp;
        if(list1.val> list2.val) {
            fakeHead.next = q;
            tmp = q;
            q= q.next;
        }
        else {
            fakeHead.next = p;
            tmp =p;
            p = p.next;
        }
        while (p!=null&&q!=null)
        {
            if(p.val< q.val)
            {
                tmp.next = p;
                p = p.next;
                tmp = tmp.next;
            }else
            {
                tmp.next =q;
                q= q.next;
                tmp = tmp.next;
            }
        }
        if(p!=null)
        {
            tmp.next=p;
        }
        if(q!=null)
        {
            tmp.next = q;
        }
    return fakeHead.next;
    }
}
